//
//  main.c
//  03-快速排序
//
//  Created by zhongad on 2017/1/10.
//  Copyright © 2017年 zhongad. All rights reserved.
//

#include <stdio.h>
#include "Swap.h"
#include <time.h>
#include <stdlib.h>

#pragma mark - 迭代法

typedef struct _Range {
    int start, end;
} Range;

Range new_Range(int s, int e) {
    Range r;
    r.start = s;
    r.end = e;
    return r;
}

void quick_sort(int arr[], const int len) {
    if (len <= 0)
        return; // 避免len等于负值时宣告堆叠数组当机(死机)
    // r[]模拟堆叠，p为数量，r[p++]为push，r[--p]为pop且取得元素
    Range r[len];
    int p = 0;
    r[p++] = new_Range(0, len - 1);
    while (p) {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        int mid = arr[range.end];
        int left = range.start, right = range.end - 1;
        while (left < right) {
            while (arr[left] < mid && left < right)
                left++;
            while (arr[right] >= mid && left < right)
                right--;
            if (left < right)
                swap(&arr[left], &arr[right]);
        }
        if (arr[left] >= arr[range.end])
            swap(&arr[left], &arr[range.end]);
        else
            left++;
        r[p++] = new_Range(range.start, left - 1);
        r[p++] = new_Range(left + 1, range.end);
    }
}

// 所用时间:0.001342
int main(int argc, const char * argv[]) {
    // 计算时间
    int arr[10000];
    for (int i = 0; i < 10000; i++) {
        arr[i] = random() % 1000000;
    }
    int len = (int) sizeof(arr) / sizeof(*arr);
    clock_t start, end;
    start = clock();
    quick_sort(arr, len);
    end = clock();
    printf("所用时间:%f\n", (double)(end - start) / CLOCKS_PER_SEC);
    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}
